package com.ljy.my_study.leetcode.子集II;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/11/15 14:20
 */
public class TestMain {

//    给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
//
//    解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
//
//             
//
//    示例 1：
//
//    输入：nums = [1,2,2]
//    输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
//    示例 2：
//
//    输入：nums = [0]
//    输出：[[],[0]]
//             
//
//    提示：
//
//            1 <= nums.length <= 10
//            -10 <= nums[i] <= 10
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/subsets-ii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    public static void main(String[] args) {
        int[] nums=new int[]{1,2,2,4,4,5,6,7,7,8};
        System.out.println(new TestMain().subsetsWithDup(nums));
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> set=new LinkedHashSet<>();
        set.add(new ArrayList<>());
        dfs(nums,0,set,new ArrayList<>());
        return new ArrayList<>(set);
    }

    public void dfs(int[] nums, int index, Set<List<Integer>> result, List<Integer> list){
        int length=nums.length;
        if(index>=length){
            return;
        }
        for(int i=index;i<length;i++){
            list.add(nums[i]);
            if(!result.contains(list)){
                result.add(new ArrayList<>(list));
                dfs(nums,i+1,result,list);
            }
            list.remove(list.size()-1);
        }
    }
}
